﻿/*
题目：得到山形数组的最少删除次数

我们定义 arr 是 山形数组 当且仅当它满足：

arr.length >= 3
存在某个下标 i （从 0 开始） 满足 0 < i < arr.length - 1 且：
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
给你整数数组 nums​ ，请你返回将 nums 变成 山形状数组 的​ 最少 删除次数。

https://leetcode.cn/problems/minimum-number-of-removals-to-make-mountain-array/description/?envType=daily-question&envId=2023-12-23
*/

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <array>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>
#include <random>

using namespace std;

class Solution {
public:
    // **KEY** 求解最长递增和最长递减可以合并成一个函数

    // upper_bound 是找到第一个可以插入的    > 
    // lower_bound 是找到最后一个可以插入的  >= 
    int minimumMountainRemovals(vector<int>& nums) {
        vector<int> incr_ar = get_LIS_array(nums);
        vector<int> decr_ar = get_LIS_array({ nums.rbegin(), nums.rend() });
        reverse(decr_ar.begin(), decr_ar.end());


        int mins = INT_MAX;
        for (int i = 1; i < nums.size() - 1; i++) {
            // "山峰"：递增或者递减必须 > 1
            if (incr_ar[i] > 1 && decr_ar[i] > 1) {
                int tmp = nums.size() - incr_ar[i] - decr_ar[i] + 1;
                mins = min(tmp, mins);
            }
        }

        return mins;
    }

    // 获得最长递增子序列
    vector<int> get_LIS_array(const vector<int>& nums) {
        vector<int> ar;     // 记录最长子序列长度

        vector<int> seq;
        seq.emplace_back(nums[0]);
        ar.emplace_back(1);

        for (int i = 1; i < nums.size(); i++) {
            int index = lower_bound(seq.begin(), seq.end(), nums[i]) - seq.begin();
            if (index == seq.size())    seq.emplace_back(nums[i]);
            else                        seq[index] = nums[i];

            ar.emplace_back(seq.size());
        }

        return move(ar);
    }
};
